package sword.offer;

import java.util.HashMap;
import java.util.Objects;

/**
 * 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
 * @link https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FortyEight {
    /**
     * 滑动窗口
     * 用字符串abcabcbb举例
     * 用两个指针指向第一个元素
     * 然后将这个元素作为key 其下标作为value 存放到map中。
     * 然后移动其中一个指针 指向下一个元素，判断其是否存在map中
     * 当 指针移动到第四个元素的时候 发现在map中存在
     * 我们记录两个指针的距离 为3 默认的最大值为1(为0的情况已经处理)  则更新最大值为3
     * 然后将第一个指针移动到重复元素的后一个，即第一个a的后一个 指向了第二个元素b
     * 然后第二个指针继续往后移 重复前面的步骤
     * */
    class Solution {
        public int lengthOfLongestSubstring(String s) {
            if(Objects.isNull(s) || s.length() == 0){
                return 0;
            }
            HashMap<Character,Integer> map = new HashMap<>();
            int max = 1;
            map.put(s.charAt(0), 0);
            int i = 0,j = 1;
            for (; j < s.length(); j++) {
                char currChar = s.charAt(j);
                if(map.containsKey(currChar)){
                    max = Math.max(j-i, max);
                    int temp = i;
                    i = map.get(currChar) + 1;
                    while(temp < i){
                        map.remove(s.charAt(temp));
                        temp++;
                    }
                }
                map.put(s.charAt(j), j);
                max = Math.max(j-i+1, max);
            }
            return max;
        }
    }

    class Solution1 {
        public int lengthOfLongestSubstring(String s) {
            int i = -1;
            int j=0;
            int max = 0;
            HashMap<Character, Integer> map = new HashMap<>();
            for (; j < s.length(); j++){
                if(map.containsKey(s.charAt(j))){
                    // 注意这一行 十分重要 不让i往回走
                    i = Math.max(i,map.get(s.charAt(j)));
                }
                map.put(s.charAt(j), j);
                max = Math.max(max, j-i);
            }
            return max;
        }
    }
}
